//
// Created by Tan Ke on 2023/12/1.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxProfit(int* prices, int pricesSize)
{
    int result = 0;
    int tempMax = 0;
    int *maxPriceList = (int*)malloc(sizeof(int) * pricesSize);

    for (int i = pricesSize - 1; i >= 0; i --) {
        if (prices[i] > tempMax) {
            tempMax = prices[i];
        }
        maxPriceList[i] = tempMax;
    }

    for (int i = 0; i < pricesSize - 1; i ++) {
        int val = maxPriceList[i + 1] - prices[i];
        if (val < 0) {
            continue;
        }
        if (val > result) {
            result = val;
        }
    }

    return result;
}

int main(void)
{
    int nums[5] = {7, 6, 4, 3, 1};
    printf("%d\n", maxProfit(nums, 5));

    int nums1[6] = {7, 1, 5, 3, 6, 4};
    printf("%d\n", maxProfit(nums1, 6));
    return 0;
}
